#Wstęp
W niniejszym raporcie będziemy porównywać metodę k–średnich oraz k–medoidów.
Posłużymy się do tego celu syntetycznymi danymi do benchmarków – zbiorze a1.
Posiada on \(3000\) obserwacji oraz \(20\) klastrów. Rozkład przeskalowanych danych wraz z oryginalnymi etykietami prezentujemy na poniższym wykresie:
ggplot(data = dataset, aes(x = x, y = y, color = as.factor(label))) +
geom_point()
Teraz dokonamy klasteryzacji korzystając z funkcji kmeans (metoda k–średnich) z wbudowanego pakietu stats oraz z funkcji pam (metoda k–medoidów) z pakietu cluster. Liczbę klastrów (parametr k) będziemy wybierać spośród zbioru liczb naturalnych od \(2\) do \(30\).
Na poniższych wykresach zaprezentujemy przykładowe klasteryzacje:
Spróbujemy teraz wybrać optymalną liczbę wykresów na podstawie błędu w klastrach:
Jak widać, metoda k–średnich zwróciła dość nieregularne wyniki (pojawiają się skoki wartości błedu), podczas gdy metoda k–medoidów w tym przypadku daje jednostajny spadek wartości funkcji celu w zależności od wartości parametru k.
Dla pierwszego algorytmów wybór najlepszego k nie będzie jednoznaczny – propozycjami (na podstawie wykresu, korzystając z tzw. metody łokcia) mogłyby być wartości \(8, 10\) lub \(20\). Dla drugiego algorytmu można zaproponować wartości \(18\) lub \(20\). Jako że \(20\) w obu przypadkach pojawia się w proponowanych, a ponadto wiemy, że jest to faktyczna liczba klastrów, ja zdecydowałbym się ją wybrać jako ostateczną wartość w obu przypadkach.
Spójrzmy teraz, jak wyglądają klastry dla wybranej liczby k
ggplot(data = cbind(dataset[, 1:2], cluster = kmeans_clusters[[19]]$cluster),
aes(x = x, y = y, group = cluster)) +
geom_point(alpha = 0.7) +
stat_voronoi(data = as.data.frame(kmeans_clusters[[19]]$centers),
aes(x = x, y = y),
color = "red", size = 3, alpha = 0.9,
geom = "path", outline = data.frame(x = c(-2, -2, 2, 2),
y = c(-2.5, 2, 2, -2.5),
group = c(1,1,1,1))) +
stat_voronoi(data = as.data.frame(pam_clusters[[19]]$medoids),
aes(x = x, y = y),
color = "blue", size = 3, alpha = 0.9,
geom = "path", outline = data.frame(x = c(-2, -2, 2, 2),
y = c(-2.5, 2, 2, -2.5),
group = c(1,1,1,1)))
Na wykresie, niebieskie wielokąty reprezentują granicę klastrów k–medoidów, natomiast czerwone – k–średnich. Jak widzimy, klastry pam są bardziej zwarte niż klastry kmeans i reprezentują niemal idealny podział na grupki danych oryginalnych.
ggplot(data = (dataset[, 1:2]), aes(x = x, y = y)) +
geom_point(alpha = 0.7) +
geom_point(data = as.data.frame(kmeans_clusters[[19]]$centers),
aes(x = x, y = y),
color = "red", size = 5) +
geom_point(data = as.data.frame(pam_clusters[[19]]$medoids),
aes(x = x, y = y),
color = "blue", size = 5)
Na wykresie na niebiesko zaznaczone są k–medoidy, na czerwono k–średnie.
Główną różnicą pomiędzy centrami klastrów wynika z faktu różnicy między działaniem algorytmu – algorytm k–średnich wybiera pewną średnią między grupą punktów – i średnia ta sama niekoniecznie musi być punktem ze zbioru danych, podczas gdy w przypadku algorytmu k–medoidów środek klastra musi należeć do zbioru danych. Stąd w przypadku pierwszego algorytmu mogą powstawać takie sytuacje jak na powyższych wykresach – jeden z klastrów zawiera w sobie dwa dosyć wyraźnie odseparowane klastry.
Na koniec porównamy tempo zbieżności obu algorytmów. Policzymy czas zbieżności dla k \(= 10, \dots, 30\).
benchmark %>%
mutate( k = as.numeric(stri_sub(test, 1, 2)),
algorithm = stri_sub(test, 4)) %>%
select(k, algorithm, elapsed) %>%
ggplot(aes(x = k, y = elapsed, color = algorithm)) +
geom_line() +
ggtitle("estimated convergency time (in seconds)")
Jak widzimy, algorytm k–medoidów z powodu swojej kwadratowej złożoności obliczeniowej jest wielokrotnie wolniejszy od błyskawicznego algorytmu k–średnich.
Algorytm k–medoidów będzie się sprawdzał lepiej niż algorytm k–średnich, gdy klastry są nie tak wyraźnie odseparowane, lecz każdy z nich ma rozkład w przybliżeniu normalny względem każdej ze zmiennych – w takim przypadku, nawet jeśli klastry na siebie nachodzą, względnie łatwo będzie wydzielić ich medianę, podczas gdy ze średnią może być trudniej. Algorytm ten będzie raczej nieskuteczny przy małej liczbie danych – wtedy również mediana będzie dla niego niewidoczna, jako że żadna z obserwacji może nie być blisko “prawdziwej” mediany rozkładu. Należy też pamiętać o jego znacznie dłuższym czasie obliczania.